package arr

func binarySearch(in []int, target int) (idx int) {
	left, right := 0, len(in)-1
	for left <= right {
		mid := left + (right-left)/2
		if in[mid] == target {
			return mid
		} else if in[mid] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return -1
}

func binarySearchI(in []int, target int) (idx int) {
	left, right := 0, len(in)-1
	for left <= right {
		mid := left + (right-left)/2
		if in[mid] == target {
			return mid
		} else if in[mid] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return -1
}

func removeElement(in []int, target int) (idx int) {
	var j = 0
	// [2,3,2,3] 3
	for i := 0; i < len(in); i++ {
		if in[i] != target {
			in[j] = in[i]
			j++
		}
	}
	return j
}

func removeElementI(in []int, target int) (idx int) {
	var j = 0
	for i := 0; i < len(in); i++ {
		if in[i] != in[j] {
			in[i] = in[j]
			j++
		}
	}
	return j
}

// 求平方然后排序
func sortedSquares(in []int) []int {
	n := len(in)
	ans := make([]int, n)
	for i, j, pos := 0, n-1, n-1; i <= j; {
		if in[i]*in[i] > in[j]*in[j] {
			ans[pos] = in[i] * in[i]
			i++
		} else {
			ans[pos] = in[j] * in[j]
			j--
		}
		pos--
	}
	return ans
}

// 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

// 示例：

// 输入：s = 7, nums = [2,3,1,2,4,3]
// 输出：2
// 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

func minSubArrayLen(s int, nums []int) int {
	var left, right, sum, minCount = 0, 0, 0, len(nums)
	for right < len(nums) {
		sum += nums[right]
		right++
		for sum >= s {
			minCount = min(minCount, right-left)
			sum -= nums[left]
			left++
		}
	}
	if minCount == len(nums) {
		return 0

	}
	return minCount
}

func minSubArrayLenI(s int, nums []int) int {
	sum, left, right, minCount := 0, 0, len(nums)-1, len(nums)-1
	for right < len(nums) {
		sum += nums[right]
		right++
		if sum >= s {
			minCount = min(minCount, right-left)
			sum -= nums[left]
			left++
		}
	}
	if minCount == len(nums) {
		return 0
	}
	return minCount
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

// 给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

// 示例:

// 输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
// spiralOrder 螺旋矩阵
func spiralOrder(n int) [][]int {
	res := make([][]int, n)
	for i := 0; i < n; i++ {
		res[i] = make([]int, n)
	}
	left, right, top, bottom := 0, n-1, 0, n-1
	num := 1
	for left <= right && top <= bottom {
		for i := left; i <= right; i++ {
			res[top][i] = num
			num++
		}
		top++
		for i := top; i <= bottom; i++ {
			res[i][right] = num
			num++
		}
		right--
		for i := right; i >= left; i-- {
			res[bottom][i] = num
			num++
		}
		bottom--
		for i := bottom; i >= top; i-- {
			res[i][left] = num
			num++
		}
		left++
	}
	return res
}

func spiralOrderI(n int) [][]int {
	res := make([][]int, n)
	for i := 0; i < n; i++ {
		res[i] = make([]int, n)
	}
	left := 0
	top := 0
	right := n - 1
	bottom := n - 1
	num := 1
	for left <= right && bottom <= top {
		for i := left; i <= right; i++ {
			res[top][i] = num
			num++
		}
		top++
		for i := top; i <= bottom; i++ {
			res[i][right] = num
			num++
		}
		right--
		for i := right; i >= left; i-- {
			res[bottom][i] = num
			num++
		}
		bottom--
		for i := bottom; i >= top; i-- {
			res[i][left] = num
			num++
		}
		left++
	}
	return res
}
